#! /usr/bin/env python
# -*- coding: utf-8 -*-
# vim:fenc=utf-8
#
# Copyright © 2019 crane <crane@crane-pc>
#
# Distributed under terms of the MIT license.

"""
https://www.lintcode.com/problem/isomorphic-strings/description
"""

from pprint import pprint
from collections import defaultdict


class Solution:
    """
    @param s: a string
    @param t: a string
    @return: true if the characters in s can be replaced to get t or false
    """
    def isIsomorphic(self, s, t):
        # return self.method1(s, t)
        # return self.method2(s, t)
        return self.method3(s, t)

    def method1(self, s, t):
        iso_map_s = {}
        iso_map_t = {}
        l = len(s)

        if l != len(t):
            return False

        for idx in range(l):
            sc = s[idx]
            tc = t[idx]
            ms = iso_map_s.get(sc)
            mt = iso_map_t.get(tc)

            if ms is None and mt is None:
                iso_map_s[sc] = tc
                iso_map_t[tc] = sc
                # print(idx, sc, tc, ms, mt)
            elif (ms is not None) and (mt is not None):
                if ms != tc or mt != sc:
                    print("hit 2")
                    return False
                # print(idx, sc, tc, ms, mt)
            else:
                # print(idx, sc, tc, ms, mt)
                # print("hit 1")
                return False

        return True

    def method2(self, s, t):
        return self.method2_part(s, t) and self.method2_part(t, s)

    def method2_part(self, s, t):
        iso_map_s = {}
        l = len(s)

        if l != len(t):
            return False

        for idx in range(l):
            sc = s[idx]
            tc = t[idx]
            ms = iso_map_s.get(sc)

            if ms is None:
                iso_map_s[sc] = tc
            elif ms != tc:
                return False

        return True


    def method3(self, s, t):
        iso_map_s = defaultdict(set)
        iso_map_t = defaultdict(set)
        l = len(s)

        for idx in range(l):
            sc = s[idx]
            tc = t[idx]

            # if len(iso_map_s[sc]) != len(iso_map_t[tc]):
            #     print('hit1 ', idx)
            #     return False

            iso_map_s[sc].add(tc)
            iso_map_t[tc].add(sc)

            if len(iso_map_s[sc]) != 1 or len(iso_map_t[tc]) != 1:
                # print('hit2 ', idx)
                return False

        return True


def test():
    s = Solution()
    assert s.isIsomorphic("abc", "def")
    assert s.isIsomorphic("aba", "bcb")

    s1 = "a`%ii,VEZQc_BSU%ObO5<sX81B/bOw+CNUd#Uav*P!Ax!#>hh,k#b/|>4ixFQZl+l!?bJjakbQbGglEb<g>Hf81m@A9GIvbd]qh?y__t+E(Iyv7zUEfZF{81VaM-0u?]tG=_fFR/XJ=X{-,oRpxE9u*VNYlM"
    s2 = "b`%ii-WE[Qc_BSV%OcO5<sX82B/cOw+CNVd#Vbv*P!Bx!#?hh-k#c/|?4ixFQ[l+l!?cJkbkcQcGhlEc<h?Hf82m@B9GIvcd]rh?y__t+E(Iyv7{VEf[F{82WbN/0u?]tG=_fFR/XJ=X{/-oRpxE9u*WNYlN"
    assert not s.isIsomorphic(s1, s2)

def main():
    print("start main")
    test()

if __name__ == "__main__":
    main()
